package org.lql.algo.codecrush.week007;

/**
 * @author: liangqinglong
 * @date: 2025-08-18 13:29
 * @description: 33. 搜索旋转排序数组 <a href="https://leetcode.cn/problems/search-in-rotated-sorted-array/description/">...</a>
 **/
public class SearchRotate {

	public int search(int[] nums, int target) {
		int left = -1;
		int right = nums.length - 1;
		while (left < right) {
			int mid = (left + right) / 2;
			if (nums[mid] <= nums[right]) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		// 旋转点
		int k = right;
		// [0, ... k, ... n]
		// 判断target所在的区间
		if (nums[k] <= target && target <= nums[nums.length - 1]) {
			return bs(k, nums.length - 1, nums, target);
		} else {
			return bs(0, k - 1, nums, target);
		}
	}

	public int bs(int left, int right, int[] nums, int target) {
		while (left <= right) {
			int mid = (left + right) / 2;
			if (nums[mid] == target) {
				return mid;
			}
			if (nums[mid] < target) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		int[] nums = {4,5,6,7,0,1,2};
		int target = 0;
		SearchRotate sr = new SearchRotate();
		int res = sr.search(nums, target);
		System.out.println(res);
	}
}
